This invention was made with government support under grant number CCR-9357790 awarded by the National Science Foundation. The government has certain rights in the invention.
Computer graphics, computer-aided design, key frame animation, 3D modeling, graphic design, font design, pen-and-ink illustration, as well as many other examples, all require the ability to edit or smooth a figure. The figures generated in these fields can be easily represented using curves that are capable of being depicted at different resolutions, i.e., multiresolution curves. For example, in computer-aided design, cross-sectional curves are frequently used in the specification of surfaces. In 3D modeling and animation, "backbone" curves can be manipulated to specify object deformations. Further, in graphic design, curves can be used to describe regions of constant color or texture. Finally, in font design, curves can be used to represent the outlines of characters.
Various forms of editing figures through computer graphic manipulation are presently known in the art. For example, hierarchical B-splines have been employed to address the problem of editing the overall form of a surface while maintaining its details. This type of formulation, as described in Forsey and Bartels, "Hierarchical B-Spline," Computer Graphics 22(4):205-212, 1988, requires the user to design an explicit hierarchy into the representative model. Further, Forsey and Bartels, "Curves and Surfaces in Computer Vision and Graphics," SPIE Proceedings 1610:88-96, 1991, describes a method of editing that recursively fits a hierarchical surface to a set of data by first fitting a course approximation and then refining in areas where the residual is large. However, when using this method, there are an infinite number of possible representations for the same surface.
In Fowler, "Geometric Manipulation of Tensor Product Services," Proceedings of the 1992 Symposium on Interactive 3D Graphics, March 1992, and Welch and Witkin, "Variational Surface Modeling," Computer Graphics 26(2):157-166, 1992, methods of editing that can be performed over narrower or broader regions of a surface are described. However, none of these methods have attempted to preserve the higher-resolution detail beneath an edited region. Further, there has been no way to obtain a unique representation for a given shape using these methods. Finally, none of the above-mentioned methods have the ability to edit a curve at any continuous level of detail nor do they have any ability to change a curve's character without affecting its overall sweep.
A figure may be presented in many ways, one convenient form of representation uses at least one multiresolution B-spline curve. Multiresolution B-spline curves are well-known in the prior art and a person of skill in the art is familiar with them, as described in many of the publications cited herein. The multiresolution B-spline curve can be expressed as a discrete signal C.sup.n and represented by a column vector of samples [c.sub.1.sup.n, . . . , c.sub.m.sup.n ].sup.T. These samples c.sub.i.sup.n can be thought of as the curve's control points in tow-dimensional space.
The following slightly generalized version of multiresolution analysis is convenient for representing figures made up of open curves, as is known in the prior art. For further discussion on this form of analysis, see Lounsbery, DeRose, Warren, "Multiresolution Surfaces of Arbitrary topological Type," Technical Report 39-10-05B, University of Washington, Dept. of Computer Science and Engineering, January 1994.
Initially, a curve expressed by a discrete signal C.sup.n that uses m samples, or control points, can be filtered by an analysis filter A.sup.n to create a low-resolution version C.sup.n-1. The low resolution version C.sup.n-1 uses m' samples, which is less than the m samples used by the discrete signal C.sup.n. Filtering and down sampling of the m samples of C.sup.n will create the m' samples of C.sup.n-1. This process can be expressed by the following matrix equation: EQU C.sup.n-1 =A.sup.n C.sup.n ( 1)
where A.sup.n is an m'.times.m matrix.
Since C.sup.n-1 contains fewer samples than C.sup.n, it is intuitively clear that some amount of detail is lost in this filtering process. However, if A.sup.n is appropriately chosen, it is possible to capture the lost detail of C.sup.n as another signal D.sup.n-1 using analysis filter B.sup.n. This separated detail can be obtained by the following matrix equation: EQU D.sup.n-1 =B.sup.n C.sup.n ( 2)
where B.sup.n is an (m-m').times.m matrix, which is related to matrix A.sup.n. This process of separating the representation of the figure, signal C.sup.n, into a low-resolution version C.sup.n-1 and detail D.sup.n-1 is called decomposition. The advantage of saving the detail D.sup.n-1 is that the original signal C.sup.n can be recovered from C.sup.n-1 and D.sup.n-1 by using another pair of matrices P.sup.n and Q.sup.n, called synthesis filters, as follows: EQU C.sup.n =P.sup.n C.sup.n-1 +Q.sup.n D.sup.n-1 ( 3)
This recovery of C.sup.n from C.sup.n-1 and D.sup.n-1 is called reconstruction.
The procedure for separating C.sup.n into a low-resolution part C.sup.n-1 and a detail part D.sup.n-1 can be applied recursively to the new signal C.sup.n-1 in a process know as a filter bank. Thus, the original signal can be expressed as a hierarchy of lower-resolution signals C.sup.0, . . . , C.sup.n-1 and details D.sup.0, . . . , D.sup.n-1, as shown in FIGS. 12A-C.
Since the original signal C.sup.n can be recovered from the sequence C.sup.0, D.sup.0, D.sup.1, . . . , D.sup.n-1, this sequence can be thought of as a transform of the original signal, and is known as a wavelet transform. One advantage to using the wavelet transform is that the total size of the transform C.sup.0, D.sup.0, . . . , D.sup.n-1 is the same as that of the original signal C.sup.n, so no extra storage is required.
Wavelet transforms have a number of properties that make them attractive for signal processing. For example, if the filters A.sup.j, B.sup.j, P.sub.j, and Q.sup.j are constructed to be sparse, then the filter bank operation can be performed very quickly, often in O(m) time. Also, for many of the signals encountered in practice, a large percentage of the entries in the wavelet transform are negligible. Wavelet compression methods can therefore approximate the original set of samples in C.sup.n by storing only the significant coefficients of the wavelet transform.
Wavelets have a variety of applications, for example, wavelets have been used in signal analysis, as discussed in Mallat, "A theory for Multiresolution Signal Decomposition: The Wavelet Representation," IEEE transactions on Pattern Analysis and Machine Intelligence 11(7):674-693, July 1989. Wavelets have also been used in image processing and numerical analysis, as discussed in DeVore, Jawerth, and Lucier, "Image Compression Through Wavelet Transform Coding," IEEE Transactions on Information Theory 38(2):719-746, March 1992 and Beylkin, Coifman and Rokhlin, "Fast Wavelet Transforms and Numerical Algorithm I," Communications on Pure and Applied Mathematics 44:141-183, 1991, respectively.
All that is required for performing a wavelet transform is an appropriate set of analysis and synthesis filters A.sup.j, B.sup.j, P.sup.j, and Q.sup.j. To see how to construct these filters, each signal C.sup.n is associated with a function f.sup.n (u) with u.epsilon.[0, 1] given by: EQU f.sup.n (u)=.PHI..sup.n (u)C.sup.n ( 4)
where .PHI..sup.n (u) is a row matrix of basis functions [.phi..sub.1.sup.n (u), . . . , .phi..sub.m.sup.n (u)], called scaling functions. The scaling functions can be endpoint-interpolating B-splines basis functions, making the function f.sup.n (u) an endpoint-interpolating B-spline curve.
The scaling functions are required to be refinable; that is, for all j in [1, n] there must exist a matrix P.sup.j such that EQU .PHI..sup.j-1 =.PHI..sup.j P.sup.j ( 5)
In other words, each scaling function at level j-1 must be expressible as a linear combination of "finer" scaling functions at level j. As suggested by the notation, the refinement matrix in equation (5) turns out to be the same as the synthesis filter P.sup.j.
Next, let V.sup.j be the linear space spanned by the set of scaling functions .PHI..sup.j. The refinement condition of .PHI..sup.j implies that these linear spaces are nested: V.sup.0 .OR right.V.sup.1 .OR right.. . . .OR right.V.sup.n. Choosing an inner product for the basis functions in V.sup.j allows the definition of W.sup.i as the orthogonal complement of V.sup.j in V.sup.j+1, that is, the space W.sup.j whose basis functions .PSI..sup.j =[.psi..sub.1.sup.j (u), . . . , .psi..sub.m-m'.sup.j (u)] are such that .PHI..sup.j and .PSI..sup.j together form a basis for V.sup.j+1, and every .psi..sub.i.sup.j (u) is orthogonal to every .phi..sub.i.sup.j (u) under the chosen inner product. The basis functions .psi..sub.i.sup.j (u) are called wavelets.
The synthesis filter Q.sup.j can be constructed as the matrix that satisfies: EQU .PSI..sup.j-1 =.PHI..sup.j Q.sup.j. (6)
Equations (5) and (6) can be expressed as a single equation by concatenating the matrices together: EQU [.PHI..sup.j-1 .vertline..PSI..sup.j-1 ]=.PHI..sup.j [P.sup.j .vertline.Q.sup.j ]. (7)
Finally, the analysis filter A.sup.j and B.sup.j are formed by the matrices satisfying the inverse relation: ##EQU1##
Note that [P.sup.j .vertline.Q.sup.j ] and [A.sup.j .vertline.B.sup.j ].sup.T are both square matrices. Thus, ##EQU2## from which it is easy to prove a number of useful identities: EQU A.sup.j Q.sup.j =B.sup.j P.sup.j =0, (10a) EQU A.sup.j P.sup.j =B.sup.j Q.sup.j =P.sup.j A.sup.j +Q.sup.j B.sup.j =1, (10b)
where 0 and 1 are the matrix of zeros and the identity matrix, respectively.
B-splines defined on a knot sequence that is uniformly spaced everywhere except at its ends, where its knots have multiplicity 4 are commonly referred to as endpoint-interpolating cubic B-splines. The basic concepts of cubic B-spline curves are discussed in detail in many texts on computer-aided design, such as Bartels, Beatty, and Barsky, An Introduction to Splines for Use in Computer Graphics and Geometric Modeling, Morgan Kaufman, 1987; Farin Curves and Surfaces for Computer Aided Geometric Design, Academic Press, 3rd ed., 1992; and Hoschek and Laser, Fundamentals, of Computer Aided Geometric Design, A. K. Peters, Ltd., Wellesley, Mass., 3rd ed. 1992.
To construct multiresolution curves from endpoint-interpolating cubic B-splines, several choices must be made. Initially, the scaling functions .PHI..sup.j (u) should be chosen for all j in [0, n]. The chosen scaling functions determine the synthesis filters P.sup.j. Further, for each level j, there should be a basis for the endpoint-interpolating cubic B-spline curves for 2.sup.j interior segments. The basis functions for these curves are the 2.sup.j +3 endpoint-interpolating cubic B-splines, which are refinable, as is required by equation (5), discussed above. Secondly, an inner product for any two functions f and g in linear space V.sup.j should be chosen. This chosen determines the orthogonal complement spaces W.sup.j. In this case, the standard form &lt;f, g&gt;=.intg.f(u)g(u)du can be used. Finally, a set of wavelets .psi..sup.j (u) that span W.sup.j should be selected. This choice determines the synthesis filters Q.sup.j. Together, the synthesis filters P.sup.j and Q.sup.j can determine the analysis filters A.sup.j and B.sup.j, as shown in equation (9). It is preferable to use the set of 2.sup.j minimally-supported functions that span W.sup.j. Given the teachings of this disclosure, those of skill in the art will be able to make the particular choices most beneficial for the scaling functions, inner product, and a set of wavelets; examples of each are given herein only as a guide, and others may be used.
As discussed above, multiresolution analysis is completely determined by an initial set of scaling functions .PHI..sup.0 and a pair of synthesis filters P.sup.j and Q.sup.j for every level j in [1, n]. The following shown in FIGS. 13A-E are some examples of endpoint-interpolating cubic B-spline scaling functions and wavelets.
Initial scaling functions are given by the four cubic Bernstein polynomials: EQU .PHI..sup.0 (u)=[(1-u).sup.3, 3u(1-u).sup.2, 3u.sup.2 (1-u),u.sup.3 ](11)
FIGS. 14 A-G depict the matrices P.sup.j and Q.sup.j for the scaling functions discussed above. Note that P.sup.j is a matrix with dimensions (2.sup.j +3).times.(2.sup.j-1 +3) whose middle columns, for j.gtoreq.3, are given by vertical translates of the fourth column, shifted down by two places for each column. Matrix Q.sup.j has the same structure for j.gtoreq.4, except with dimensions (2.sup.j +3) .times.2.sup.j-1.
The P.sup.j matrix is a straightforward derivation form the Cox-de Boor recursion formula, as discussed in Farin, Curves and Surfaces for Computer Aided Geometric Design, Academic Press, 3rd ed., 1992. The formula encodes how each endpoint-interpolating B-spline can be expressed as a linear combination of B-splines that are half as wide. To derive the Q.sup.j matrix, some new notation is used. Given two row vectors of functions X and Y, let [&lt;X.vertline.Y&gt;] be the matrix of inner products (X.sub.k, Y.sub.1). Since, by definition, scaling functions an wavelets at the same level j are orthogonal, it follows that: EQU [&lt;.PHI..sup.j .vertline..PSI..sup.j &gt;]=[&lt;.PHI..sup.j .vertline..PHI..sup.j+1 &gt;]Q.sup.j+1 =0 (12)
so the columns of Q.sup.j+1 span the null space of [&lt;.PHI..sup.j .vertline..PHI..sup.j+1 &gt;]. A basis for this null space can be chosen by finding the matrix Q.sup.j+1 that has columns with the shortest runs of non-zero coefficients; this matrix corresponds to the wavelets with minimal support. The entries of the inner product matrix can be computed exactly with symbolic integration; thus, the fractions depicted in FIGS. 14A-H are exact.
A construction related to the above has also been independently proposed by Chui and Quak, Wavelets on a Bounded Interval, Numerical Methods in Approximation theory, Vol. 9, pp. 53-75, Birkhauser Verlag, Basel, 1992. Multiresolution constructions can be built for other types of splines as well, such as uniform B-splines, as discussed in Chui, An Introduction to Wavelets, Academic Press, Boston, 1992, and nonuniform B-splines with arbitrary knot sequences, as discussed in Lyche and Morken, Spline-wavelets of Minimal Support, Numerical Methods of Approximation Theory, Vol. 9, pp. 177-194, Birkhuaser Verlag, Basel, 1992.
Because both the scaling functions and wavelets have compact support, the synthesis filters P.sup.j and Q.sup.j have a banded structure, allowing reconstruction in O(m) time. However, a potential weakness of this construction is that the analysis filters A.sup.j and B.sup.j are dense, which would seem to imply an O(m.sup.2)--time decomposition algorithm. Fortunately, there is a shortcut method, described in Quak and Weyrich, "Decomposition and Reconstruction Algorithms for Spline Wavelets on a Bounded Interval," CAT Report 294, Center for Approximation Theory, Texas A&M University, April 1993, for performing the decomposition in linear time. The algorithm for performing the algorithm in linear time, uses a transformation to the "dual space." The following is a summarization of how the linear-time algorithm can be implemented.
Let I.sup.j and J.sup.j be the inner product matrices [&lt;.PHI..sup.j .vertline..PHI..sup.j &gt;] and [&lt;.PSI..sup.j .vertline..PSI..sup.j &gt;], respectively. Equations (1) and (2) can then be rewritten: EQU I.sup.j-1 C.sup.j-1 =(P.sup.j).sup.T I.sup.j C.sup.j ( 13a) EQU J.sup.j-1 D.sup.j-1 =(Q.sup.j).sup.T I.sup.j C.sup.j. (13b)
Since, P.sup.j, Q.sup.j, and I.sup.j are banded matrices the right-hand side of these equations can be computed in linear time. What remains are two-band diagonal systems of equations, which can also be solved in linear time using LU decompositions, as discussed in Press, Flannery, Teukolsky and Fetterling, Numerical Recipes, University Press, Cambridge, second edition, 1992.
The matrix I.sup.j for j.gtoreq.3 is shown in FIG. 14H. Note the I.sup.j is a symmetric matrix with dimensions (2.sup.j +3).times.(2.sup.j +3) whose middle columns for j.gtoreq.3, are given by vertical translates of the sixth column. The I.sup.j matrices for j&lt;3 and the J.sup.j matrices can be determined with the following equations: EQU I.sup.j =(P.sup.j+1).sup.T I.sup.j+1 P.sup.j+1 ( 14a) EQU J.sup.j =(Q.sup.j+1).sup.T I.sup.j+1 Q.sup.j+1 ( 14b)
An even better approach than discribed in Quak and Weyrich involves computing C.sup.j-1 and D.sup.j-1 from C.sup.j by solving the sparse linear system: ##EQU3##
The matrix [P.sup.j .vertline.Q.sup.j ] can then be made into a banded matrix simply by interspersing the columns of P.sup.j and Q.sup.j. The resulting banded system can then be solved in linear time using LU decomposition, as described in Press, Flannery, Teukolsky, and Fetterling, Numerical Recipies, Cambridge University Press, second edition, 1992.
These are known figure editing methods for curve and surface smoothing that minimize various energy norms. However, these methods of editing are not for the multiresolution curves discussed above. A survey of these methods can be found at Hoschek and Lasser, Fundamentals of Computer-Aided Geometric Design, A. K. Peters, Ltd., Wellesley, Mass. 3rd., 1992. One method mentioned in the survey uses a fairness functional on hand-drawn curves as well as surfaces. For a more detailed description, see Celniker and Gossard, "Deformable Curve and Surface Finite Elements for Free-form Shape Design," Computer Graphics 25(4):257-265, July 1991. A disadvantage to these methods is that they do not perform least-squares type smoothing and they tend to be very complex.
Other methods for editing a figure include scan conversion of a figure using approximating curves. For examples, see Banks and Cohen, "Realtime Spline Curves From Interactively Sketched Data," Computer Graphics 24(2):99-107, 1990; Lyche and Morken, "Knot Removal for Parametric B-Spline Curves and Surfaces," Computer Aided Geometric Design 4(3):217-230, 1987; Plass and Stone, "Curve-Fitting With Piecewise Parametric Cubics," Computer Graphics 17(3):229-239, July 1983; and Schneider, Phoenix: an Interactive Curve Design System Based on The Automatic Fitting of Hand-Sketched Curves, Dept. of Computer Science & Eng., University of Washington, 1988. However, the curve fitting methods for scan conversion described in these publications usually require particular continuity constraints and have centered on various forms of knot removal for approximating the curve, thus limiting their ability to reach higher compression ratios.
In summary, although various methods of editing and smoothing a figure are known, these methods have not attempted to preserve higher-resolution detail beneath the edited region. Further, these methods have not been able to edit a figure at any continuous level of detail or change a figure's character without changing its sweep. These limitations greatly reduce the type of editing capabilities available within field like computer graphics.